package org.leetcode.middle.leetcode18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution
{

    /**
     * 在三数求和的基础上再套一层for循环
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {

       List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);


        for (int i = 0; i < nums.length; i++) {


            if (nums[i]>0 && nums[i]>target)
            {
                return result;
            }

            //对i去重
            if (i>0 && nums[i]==nums[i-1])
            {
                continue;
            }

            for (int j = i+1; j < nums.length; j++) {

                //对j进行去重，"j>i+1"的作用：避免j-1代表的下标与i相同
                if (j>i+1 && nums[j-1]==nums[j])
                {
                    continue;
                }

                int left = j+1;
                int right = nums.length-1;

                while (right>left)
                {
                    int sum = nums[i]+nums[j]+nums[left]+nums[right];

                    if (sum>target){
                        right--;
                    }else if (sum<target)
                    {
                        left++;
                    }else {
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));

                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;

                    }
                }

            }

        }


        return result;
    }
    public static void main(String[] args) {

    }
}
